{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import tensorflow as tf\n",
    "from sklearn import datasets\n",
    "from tensorflow.python.framework import ops\n",
    "from tensorflow.examples.tutorials.mnist import input_data\n",
    "from sklearn.decomposition import PCA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#######################\n",
    "### Necessary Flags ###\n",
    "#######################\n",
    "\n",
    "batch_size = 50\n",
    "num_steps = 1000\n",
    "log_steps = 50\n",
    "is_evaluation = True\n",
    "gamma = -15.0\n",
    "initial_learning_rate = 0.01"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "###########################\n",
    "### Necessary Functions ###\n",
    "###########################\n",
    "def cross_class_label_fn(A):\n",
    "    \"\"\"\n",
    "    This function take the matrix of size (num_classes, batch_size) and return the cross-class label matrix\n",
    "    in which Yij are the elements where i,j are class indices.\n",
    "    :param A: The input matrix of size (num_classes, batch_size).\n",
    "    :return: The output matrix of size (num_classes, batch_size, batch_size).\n",
    "    \"\"\"\n",
    "    label_class_i = tf.reshape(A, [num_classes, 1, batch_size])\n",
    "    label_class_j = tf.reshape(label_class_i, [num_classes, batch_size, 1])\n",
    "    returned_mat = tf.matmul(label_class_j, label_class_i)\n",
    "    return returned_mat\n",
    "\n",
    "\n",
    "# Compute SVM loss.\n",
    "def loss_fn(alpha, label_placeholder):\n",
    "    term_1 = tf.reduce_sum(alpha)\n",
    "    alpha_cross = tf.matmul(tf.transpose(alpha), alpha)\n",
    "    cross_class_label = cross_class_label_fn(label_placeholder)\n",
    "    term_2 = tf.reduce_sum(tf.multiply(my_kernel, tf.multiply(alpha_cross, cross_class_label)), [1, 2])\n",
    "    return tf.reduce_sum(tf.subtract(term_2, term_1))\n",
    "\n",
    "\n",
    "# Gaussian (RBF) prediction kernel\n",
    "def kernel_pred(x_data, prediction_grid):\n",
    "    A = tf.reshape(tf.reduce_sum(tf.square(x_data), 1), [-1, 1])\n",
    "    B = tf.reshape(tf.reduce_sum(tf.square(prediction_grid), 1), [-1, 1])\n",
    "    square_distance = tf.add(tf.subtract(A, tf.multiply(2., tf.matmul(x_data, tf.transpose(prediction_grid)))),\n",
    "                             tf.transpose(B))\n",
    "    return tf.exp(tf.multiply(gamma, tf.abs(square_distance)))\n",
    "\n",
    "\n",
    "def kernel_fn(x_data, gamma):\n",
    "    \"\"\"\n",
    "    This function generates the RBF kernel.\n",
    "    :param x_data: Input data\n",
    "    :param gamma: Hyperparamet.\n",
    "    :return: The RBF kernel.\n",
    "    \"\"\"\n",
    "    square_distance = tf.multiply(2., tf.matmul(x_data, tf.transpose(x_data)))\n",
    "    kernel = tf.exp(tf.multiply(gamma, tf.abs(square_distance)))\n",
    "    return kernel\n",
    "\n",
    "\n",
    "def prepare_label_fn(label_onehot):\n",
    "    \"\"\"\n",
    "    Label preparation. Since we are dealing with one vs all scenario, for each sample\n",
    "    all the labels other than the current class must be set to -1. It can be done by simply\n",
    "    Setting all the zero values to -1 in the return one_hot array for classes.\n",
    "\n",
    "    :param label_onehot: The input as one_hot label which shape (num_samples,num_classes)\n",
    "    :return: The output with the same shape and all zeros tured to -1.\n",
    "    \"\"\"\n",
    "    labels = label_onehot\n",
    "    labels[labels == 0] = -1\n",
    "    labels = np.transpose(labels)\n",
    "    return labels\n",
    "\n",
    "\n",
    "def next_batch(X, y, batch_size):\n",
    "    \"\"\"\n",
    "    Generating a batch of random data.\n",
    "    :param x_train:\n",
    "    :param batch_size:\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    idx = np.random.choice(len(X), size=batch_size)\n",
    "    X_batch = X[idx]\n",
    "    y_batch = y[:, idx]\n",
    "    return X_batch, y_batch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Extracting MNIST_data/train-images-idx3-ubyte.gz\n",
      "Extracting MNIST_data/train-labels-idx1-ubyte.gz\n",
      "Extracting MNIST_data/t10k-images-idx3-ubyte.gz\n",
      "Extracting MNIST_data/t10k-labels-idx1-ubyte.gz\n",
      "The variance of the chosen components = %91.41\n"
     ]
    }
   ],
   "source": [
    "########################\n",
    "### Data Preparation ###\n",
    "########################\n",
    "\n",
    "# Read MNIST data. It has a data structure.\n",
    "# mnist.train.images, mnist.train.labels: The training set images and their associated labels.\n",
    "# mnist.validation.images, mnist.validation.labels: The validation set images and their associated labels.\n",
    "# mnist.test.images, mnist.test.labels: The test set images and their associated labels.\n",
    "\n",
    "# Flags:\n",
    "#      \"reshape=True\", by this flag, the data will be reshaped to (num_samples,num_features)\n",
    "#      and since each image is 28x28, the num_features = 784\n",
    "#      \"one_hot=True\", this flag return one_hot labeling format\n",
    "#      ex: sample_label [1 0 0 0 0 0 0 0 0 0] says the sample belongs to the first class.\n",
    "mnist = input_data.read_data_sets(\"MNIST_data/\", reshape=True, one_hot=True)\n",
    "\n",
    "# Label preparation.\n",
    "y_train = prepare_label_fn(mnist.train.labels)\n",
    "y_test = prepare_label_fn(mnist.test.labels)\n",
    "\n",
    "# Get the number of classes.\n",
    "num_classes = y_train.shape[0]\n",
    "\n",
    "##########################################\n",
    "### Dimensionality Reduction Using PCA ###\n",
    "##########################################\n",
    "pca = PCA(n_components=100)\n",
    "pca.fit(mnist.train.images)\n",
    "\n",
    "# print the accumulative variance for the returned principle components.\n",
    "print(\"The variance of the chosen components = %{0:.2f}\".format(100 * np.sum(pca.explained_variance_ratio_)))\n",
    "x_train = pca.transform(mnist.train.images)\n",
    "x_test = pca.transform(mnist.test.images)\n",
    "num_fetures = x_train.shape[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "############################\n",
    "### Graph & Optimization ###\n",
    "############################\n",
    "# Create graph\n",
    "sess = tf.Session()\n",
    "\n",
    "# Initialize placeholders\n",
    "data_placeholder = tf.placeholder(shape=[None, num_fetures], dtype=tf.float32)\n",
    "label_placeholder = tf.placeholder(shape=[num_classes, None], dtype=tf.float32)\n",
    "pred_placeholder = tf.placeholder(shape=[None, num_fetures], dtype=tf.float32)\n",
    "\n",
    "# The alpha variable for solving the dual optimization problem.\n",
    "alpha = tf.Variable(tf.random_normal(shape=[num_classes, batch_size]))\n",
    "\n",
    "# Gaussian (RBF) kernel\n",
    "gamma = tf.constant(gamma)\n",
    "\n",
    "# RBF kernel\n",
    "my_kernel = kernel_fn(data_placeholder, gamma)\n",
    "\n",
    "# Loss calculation.\n",
    "loss = loss_fn(alpha, label_placeholder)\n",
    "\n",
    "# Generating the prediction kernel.\n",
    "pred_kernel = kernel_pred(data_placeholder, pred_placeholder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#############################\n",
    "### Prediction & Accuracy ###\n",
    "#############################\n",
    "prediction_output = tf.matmul(tf.multiply(label_placeholder, alpha), pred_kernel)\n",
    "prediction = tf.arg_max(prediction_output - tf.expand_dims(tf.reduce_mean(prediction_output, 1), 1), 0)\n",
    "accuracy = tf.reduce_mean(tf.cast(tf.equal(prediction, tf.argmax(label_placeholder, 0)), tf.float32))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Optimizer\n",
    "train_op = tf.train.AdamOptimizer(initial_learning_rate).minimize(loss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Variables Initialization.\n",
    "init = tf.global_variables_initializer()\n",
    "sess.run(init)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step #50, Loss= -2258.316895, training accuracy= 0.360000, testing accuracy= 0.320000 \n",
      "Step #100, Loss= -4122.960938, training accuracy= 0.560000, testing accuracy= 0.540000 \n",
      "Step #150, Loss= -5949.908203, training accuracy= 0.660000, testing accuracy= 0.860000 \n",
      "Step #200, Loss= -7223.067871, training accuracy= 0.920000, testing accuracy= 0.920000 \n",
      "Step #250, Loss= -7966.063965, training accuracy= 0.980000, testing accuracy= 0.980000 \n",
      "Step #300, Loss= -9594.546875, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #350, Loss= -8474.500977, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #400, Loss= -10710.136719, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #450, Loss= -11123.141602, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #500, Loss= -10979.212891, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #550, Loss= -12162.305664, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #600, Loss= -14245.701172, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #650, Loss= -10697.230469, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #700, Loss= -14184.848633, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #750, Loss= -10400.685547, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #800, Loss= -13207.020508, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #850, Loss= -11359.216797, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #900, Loss= -17082.535156, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #950, Loss= -14653.086914, training accuracy= 1.000000, testing accuracy= 1.000000 \n",
      "Step #1000, Loss= -18085.871094, training accuracy= 1.000000, testing accuracy= 1.000000 \n"
     ]
    }
   ],
   "source": [
    "# Training loop\n",
    "for i in range(num_steps):\n",
    "\n",
    "    batch_X, batch_y = next_batch(x_train, y_train, batch_size)\n",
    "    sess.run(train_op, feed_dict={data_placeholder: batch_X, label_placeholder: batch_y})\n",
    "\n",
    "    temp_loss = sess.run(loss, feed_dict={data_placeholder: batch_X, label_placeholder: batch_y})\n",
    "\n",
    "    acc_train_batch = sess.run(accuracy, feed_dict={data_placeholder: batch_X,\n",
    "                                                   label_placeholder: batch_y,\n",
    "                                                   pred_placeholder: batch_X})\n",
    "\n",
    "    batch_X_test, batch_y_test = next_batch(x_test, y_test, batch_size)\n",
    "    acc_test_batch = sess.run(accuracy, feed_dict={data_placeholder: batch_X_test,\n",
    "                                                  label_placeholder: batch_y_test,\n",
    "                                                  pred_placeholder: batch_X_test})\n",
    "\n",
    "    if (i + 1) % log_steps == 0:\n",
    "        print('Step #%d, Loss= %f, training accuracy= %f, testing accuracy= %f ' % (\n",
    "            (i+1), temp_loss, acc_train_batch, acc_test_batch))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
